#! /usr/bin/python
import sys
import time
from heapq import *

def readCnts(f, chunk):
	cnt = [0] * 4 ** chunk
	totalCnt = 0
	s = f.read()
	n, i = 0, 0
	while s:
		for ch in s:
			if ch == 'A':
				n = n * 4
				i += 1
			elif ch == 'C':
				n = n * 4 + 1
				i += 1
			elif ch == 'G':
				n = n * 4 + 2
				i += 1
			elif ch == 'T':
				n = n * 4 + 3
				i += 1
			if i == chunk:
				cnt[n] += 1
				totalCnt += chunk
				n, i = 0, 0
		s = f.read()
	# chunk - 1 trailing characters may be ignored
	return (cnt, totalCnt)

def makeHuffTree(cnt):
	q = []
	for i in range(len(cnt)):
		q.append((cnt[i], i))
	heapify(q)

	while len(q) > 1:
		a = heappop(q)
		b = heappop(q)
		heappush(q, (a[0]+b[0], a, b))
	return q[0]

def comp(tree, cnt, depth = 0):
	if len(tree) == 2:
		return depth * cnt[tree[1]]
	else:
		return comp(tree[1], cnt, depth+1) + comp(tree[2], cnt, depth +1)

def main():
	if len(sys.argv) < 4:
		print "usage huff.py <file1> <file2> <chunk-size>"
		exit(1)

	f1 = open(sys.argv[1])
	f2 = open(sys.argv[2])
	chunk = int(sys.argv[3])

	cnt1, len1 = readCnts(f1, chunk)
	cnt2, len2 = readCnts(f2, chunk)
	tree = makeHuffTree(cnt1)
	cs = comp(tree, cnt2)
	ts = len2 * 2 # 2 bits per base
	print (1.0 - float(cs)/ts) * 100.0

main()
